#encoding=utf-8

# ECC保密通信算法例子
#1） Alice选定一条椭圆曲线E，并取椭圆曲线上一点作为基点G，假设选定E29(4,20)，基点G(13,23) , 基点G的阶数n=37
#2） Alice选择一个私有密钥k（k<n）比如25，并生成公开密钥K=kG =25G = (14,6）
#3） Alice将E和点K、G传给Bob
#4） Bob收到信息后，将待传输的明文编码到E上的一点M，并产生一个随机整数r（r<n,n为G的阶数）。
#    假设r=6 要加密的信息为3,因为M也要在E29(4,20) 上，所以M=(3,28)
#5） Bob计算点C1和C2
#    C1=M+rK=M+6K=M+6G=(3,28)+6×(14,6)=(3,28)+(27,27)=(6,12)
#    ​C2=rG=6G=(5,7)
#6） Bob将C1和C2传给Alice
#7） ​Alice收到信息后，计算C1 − kC2，结果就是
# M=C1−kC2=(6,12)−25C2=(6,12)−25×(5,7)=(6,12)−(27,27)=(6,12)+(27,2)=(3,28)


p = 29
a = 4
b = 20

k = 25
r = 6

def exgcd(a, b):
    if b == 0:
        return 1, 0, a
    else:
        x, y, q = exgcd(b, a % b)  # 递归直至余数等于0(需多递归一层用来判断)
        x, y = y, (x - (a // b) * y)  # 辗转相除法反向推导每层a、b的因子使得gcd(a,b)=ax+by成立
        return x, y, q

# 扩展欧几里得求逆元


def invert(a, p):
    x, y, q = exgcd(a, p)
    if q != 1:
        raise Exception("No solution.")
    else:
        return (x + p) % p  # 防止负数


def ECCnegative(x, y, p):
    return x, p-y


def EccAdd(x1, y1, x2, y2, p, a):
    if(x1 == x2):
        if((y1+y2) % p == 0):
            return -1, -1  # infinity return
        elif(y1 != y2):
            print("Input Error, Please check the input!")
            return -2, -2  # error input return
        else:
            k = ((3 * x1 * x1 + a) * invert(2 * y1, p)) % p
            x3 = (k * k - x1 - x2) % p
            y3 = (k * (x1 - x3) - y1) % p
            return int(x3), int(y3)
    else:
        k = ((y2 - y1) * invert(x2 - x1, p)) % p
        x3 = (k * k - x1 - x2) % p
        y3 = (k * (x1 - x3) - y1) % p
        return int(x3), int(y3)


def EccMul(k, x, y, p, a):
    tempx, tempy = -1, -1
    nowx, nowy = x, y
    while(k != 0):
        mark = k & 1
        k = k >> 1
        if(mark == 1):
            if(tempx == -1):
                tempx, tempy = nowx, nowy
            else:
                tempx, tempy = EccAdd(tempx, tempy, nowx, nowy, p, a)
        nowx, nowy = EccAdd(nowx, nowy, nowx, nowy, p, a)
    return tempx, tempy

M=(3,28)
K = EccMul(k, 13, 23, p, a)
print(type(K))
print(K)
C1 = 
C2=EccMul(r, 13, 23, p, a)

print(EccAdd(3, 28, 27, 27, p, a))